package com.example.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Leetcode1122_RelativeSortArray {
    public static void main(String[] args) {
        int[] arr1 = {2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
        int[] arr2 = {2, 1, 4, 3, 9, 6};
        int[] res = relativeSortArray2(arr1, arr2);
        for (int re : res) {
            System.out.print(re + ", ");
        }

    }

    /**
     * 解法二:快速排序的变形
     *
     * 设计一个排序算法，
     * 两个值A、B的排序规则为：
     *    如果A、B都出现在arr2则，根据在arr2中的顺序确定
     *    如果一个出现在arr2一个不出现在arr2，在出现arr2的排前面
     *    如果A、B都不在arr2出现，则根据A、B的数值大小确定顺序
     *     可基于快速排序（其他排序方式也可以改造）进行修改
     *     可以将arr2中值及顺序信息放置到Map中，便于查找
     * @param arr1
     * @param arr2
     * @return
     */
    public static int[] relativeSortArray2(int[] arr1, int[] arr2) {
        //arr2 保留顺序 放入map
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], i);
        }

        myQuickSort(arr1, 0, arr1.length - 1, map);
        return arr1;
    }

    /**
     * 解法一:暴力法
     * 先定义一个和arr1一样大的结果数组result
     * 顺序遍历arr2,
     *    当在arr1中找到arr2的元素，将其赋给result
     * @param arr1
     * @param arr2
     * @return
     */
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] result = new int[arr1.length];
        int resIndex = 0;
        // 1.先将arr2中有的数据在arr1全部按照arr2的顺序写入到result中
        for (int i = 0; i < arr2.length; i++) {
            for (int j = 0; j < arr1.length; j++) {
                if (arr2[i] == arr1[j]) {
                    result[resIndex++] = arr1[j];
                    arr1[j] = -1;
                }
            }
        }
        // 记录相对顺序和未在arr1中出现的数据的分割索引
        int spiltIndex = resIndex;

        // 2.先将未出现在arr2中的arr1的元素放到result的末尾
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != -1) {
                result[resIndex++] = arr1[i];
            }
        }
        // 最后对末尾的元素进行排序
        Arrays.sort(result, spiltIndex, arr1.length);
        return result;
    }


    /**
     * 自定义规则的快速排序
     *    如果A、B都出现在arr2则，根据在arr2中的顺序确定
     *    如果一个出现在arr2一个不出现在arr2，在出现arr2的排前面
     *    如果A、B都不在arr2出现，则根据A、B的数值大小确定顺序
     * @param arr
     * @param begin
     * @param end
     * @param map
     */
    public static void myQuickSort(int[] arr, int begin, int end, Map<Integer, Integer> map) {
        // 递归基
        if (end - begin < 2)
            return;

        // 获取轴点元素索引，经过这个过程，轴点元素之前的都比轴点元素小，之后的都比轴点元素大
        int pivotIndex = getPivotIndex(arr, begin, end,map);

        // 递归完成轴点之前的元素的排序
        myQuickSort(arr, begin, pivotIndex, map);
        // 递归完成轴点之后的元素的排序
        myQuickSort(arr, pivotIndex + 1, end, map);
    }

    /**
     * 获取轴点元素的索引位置
     * 在这个获取轴点元素的过程中会将比轴点大的元素放在轴点的右边，比轴点小的放在左边
     *
     * @param arr
     * @param begin
     * @param end
     * @param map
     * @return
     */
    private static int getPivotIndex(int[] arr, int begin, int end, Map<Integer, Integer> map) {
        int random = new Random().nextInt(end - begin) + begin;
        // 这里的交换是为了不会每次都是用第一个元素做轴点元素，可以有效避免出现最坏的情况
        int tmp = arr[begin];
        arr[begin] = arr[random];
        arr[random] = tmp;

        // 临时存储一下轴点元素
        // 在一次确定轴点的索引值中，轴点元素是不会变的！！！
        int pivot = arr[begin];
        // 当begin ==end时说明本次的轴点已经找到，才会退出循环
        while (begin < end) {
            // 这个循环控制的是从右往左遍历，一旦反向就要退出循环
            while (begin < end) {
                if (compare(arr[end], pivot, map) >= 0) {// 右边元素 > 轴点元素
                    end--;
                } else {
                    // 一旦begin,end指向的元素进行了替换换意味着换方向了，就要退出本次循环
                    arr[begin] = arr[end];
                    ++begin;
                    break;
                }
            }

            // 这个循环控制的是从左往右遍历，一旦反向就要退出循环
            while (begin < end) {
                if (compare(arr[begin], pivot, map) <= 0) {// 左边元素 < 轴点元素
                    begin++;
                } else {
                    arr[end] = arr[begin];
                    --end;
                    break;
                }
            }

        }
        // 最后，将轴点元素放回数组中
        arr[begin] = pivot;
        return begin;
    }

    //自定义比较规则
    public static int compare(int a, int b, Map<Integer, Integer> map) {
        int o1Index = map.getOrDefault(a, -1);
        int o2Index = map.getOrDefault(b, -1);

        if (o1Index == -1 && o2Index == -1) { // 两个数都没出现在arr2中, 由a,b的大小关系决定谁大
            return a - b;
        } else if (o1Index == -1) { // a出现在arr2中，但是b没出现在arrr2中，a大
            return 1;
        } else if (o2Index == -1) {// b出现在arr2中，但是a没出现在arrr2中，小
            return -1;
        } else { // 两个数都出现在arr2中, 由在arr2中的顺序决定
            return o1Index - o2Index;
        }
    }
}
